package LeetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}15:16
 */
public class LeetCode491 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<Integer> list = new ArrayList<>();
        dfs2(nums,0,list);
        return res;
    }

    public void dfs2(int[] nums,int index,List<Integer> list){
        if (index == nums.length - 1){
            return;
        }
        if (list.size() >= 2){
            res.add(new ArrayList<>(list));
        }
//        for (int j = index; j < nums.length; j++) {
//            int temp = nums[j];
            int temp = nums[index];
            list.add(temp);
            for (int i = index + 1; i < nums.length; i++) {
                if (list.contains(nums[i])){
                    continue;
                }
                if (nums[i] > temp) {
                    list.add(nums[i]);
                    dfs2(nums, i, list);
                    list.remove(list.size() - 1);
                }
            }
            list.remove(list.size() - 1);
//        }
    }

//    private List<List<Integer>> res = new ArrayList<List<Integer>>();
//    private List<Integer> temp = new ArrayList<>();
//
//    public List<List<Integer>> findSubsequences(int[] nums) {
//        if (nums == null) {
//            return null;
//        }
//        dfs(0, Integer.MIN_VALUE, nums);
//        return res;
//    }
//
//    private void dfs(int curIndex, int preValue, int[] nums) {
//        if (curIndex >= nums.length) {  // 遍历结束
//            if (temp.size() >= 2) {
//                res.add(new ArrayList<>(temp));
//            }
//            return;
//        }
//
//        if (nums[curIndex] >= preValue) {   // 将当前元素加入，并向后遍历
//            temp.add(nums[curIndex]);
//            dfs(curIndex + 1, nums[curIndex], nums);
//            temp.remove(temp.size() - 1);
//        }
//        if (nums[curIndex] != preValue) {   // 不遍历 重复元素
//            dfs(curIndex + 1, preValue, nums);  // 将下一个元素加入，并向后遍历
//        }
//    }

    // 定义全局变量保存结果
//    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> findSubsequences2(int[] nums) {
        // idx 初始化为 -1，开始 dfs 搜索。
        dfs(nums, -1, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int idx, List<Integer> curList) {
        // 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
        if (curList.size() > 1) {
            res.add(new ArrayList<>(curList));
        }

        // 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
        // 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
        Set<Integer> set = new HashSet<>();
        for (int i = idx + 1; i < nums.length; i++) {
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            // 2. 如果 nums[i] >= nums[idx] 的话，说明出现了新的递增序列，因此继续 dfs 搜索（因为 curList 在这里是复用的，因此别忘了 remove 哦）
            if (idx == -1 || nums[i] >= nums[idx]) {
                curList.add(nums[i]);
                dfs(nums, i, curList);
                curList.remove(curList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode491().findSubsequences(new int[]{4, 6, 7, 7}));
    }
}
